package 算法.leetcode.bytedance;

import 算法.leetcode.offer.base.ListNode;

/**
 * @author lchenglong
 * @date 2022/5/15
 */
public class OfferLinked_IV {
    public ListNode sortList(ListNode head) {
        // 边界
        if(head==null||head.next==null)return head;
        ListNode slow=head;
        ListNode fast=head.next;
        // 利用快慢指针将链表一分为2
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode head2=slow.next;
        slow.next=null;
        return merge(sortList(head),sortList(head2));
    }
    // 合并两个有序链表
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode curr  = dummy;

        while(l1 != null && l2!= null){ // 退出循环的条件是走完了其中一个链表
            // 判断l1 和 l2大小
            if (l1.val < l2.val){
                // l1 小 ， curr指向l1
                curr.next = l1;
                l1 = l1.next;       // l1 向后走一位
            }else{
                // l2 小 ， curr指向l2
                curr.next = l2;
                l2 = l2.next;       // l2向后走一位
            }
            curr = curr.next;       // curr后移一位
        }

        // 退出while循环之后,比较哪个链表剩下长度更长,直接拼接在排序链表末尾
        curr.next = l2==null?l1:l2;
        // 最后返回合并后有序的链表
        return dummy.next;
    }
}
